

class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }

/**
 * 160相交链表
 * https://leetcode.cn/problems/intersection-of-two-linked-lists/submissions/471007831/
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //如果两个有null的
        if(headA == null || headB == null) {
            return null;
        }
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        //分别求两链表的长度
        int len1 = 0;
        int len2 = 0;
        while(cur1 != null) {
            cur1 = cur1.next;
            len1++;
        }
        while(cur2 != null) {
            cur2 = cur2.next;
            len2++;
        }
        //量长度相减，求绝对值
        int len = Math.abs(len1 - len2);
        //长的先走len步
        cur1 = headA;
        cur2 = headB;
        if(len1 < len2) {
            for(int i = 0; i < len; i++) {
                cur2 = cur2.next;
            }
        } else {
            for(int i = 0; i < len; i++) {
                cur1 = cur1.next;
            }
        }
        //同时走
        while(cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        //两个没有相交，但都走到了null
        if(cur1 == null) {
            return null;
        }
        return cur1;
    }
}